<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title> 快速排序 </title>
</head>
<body>
    <div><img src="./快速排序.png" alt=""></div>
</body>
</html>
<script>
// 2021-06-07-夜-北京丰台- 
// 对自己的不满是任何真正有才能的人根本特征之一 

// 快速排序的特定就是快 而且效率高 它是处理大数据的最快的排序算法之一 
// 思路 
/*
    1先找到一个基准点(一般之指数组的中部) 
    2然后数组被该基准点分为两部分 依次于该基准点数据比较 如果他下 放左边 防止 放右边 
    3左右分别用一个 空数组去存储比较后的数据 
    4最后递归执行上述的操作 直到数组长度<=1 
    特定 快速 常用 
    缺点 需要另外声明两个数组 浪费了内存空间资源 
*/
//代码示例 
    const quickSort1 = arr => {
        if (arr.length <= 1) {                             //判断数组长度 
            return arr;
        }
        const midIndex = Math.floor(arr.length / 2);       //取到基准点 分
        //取基准点的值，splice(index,1) 则返回的是含有被删除的元素的数组。
        const valArr = arr.splice(midIndex, 1);
        const midIndexVal = valArr[0];
        const left = [];                 //存放比基准点小的数组
        const right = [];                //存放比基准点大的数组
                                         //遍历数组，进行判断分配
        for (let i = 0; i < arr.length; i++) {
            if (arr[i] < midIndexVal) {  //>为降序 <为升序
                left.push(arr[i]);       //比基准点小的放在左边数组
            } else {
                right.push(arr[i]);      //比基准点大的放在右边数组
            }
        }
        //递归执行以上操作，对左右两个数组进行操作，直到数组长度为 <= 1
        return quickSort1(left).concat(midIndexVal, quickSort1(right));
    };
    const array2 = [5, 4, 3, 2, 1];
    console.log('quickSort1 ', quickSort1(array2));
    // quickSort1: [1, 2, 3, 4, 5]
     

// 
// 第一，快速排序是原地排序算法吗 ？
// 因为 partition() 函数进行分区时，不需要很多额外的内存空间，所以快排是原地排序算法。

// 第二，快速排序是稳定的排序算法吗 ？
// 和选择排序相似，快速排序每次交换的元素都有可能不是相邻的，因此它有可能打破原来值为相同的元素之间的顺序。因此，快速排序并不稳定。

// 第三，快速排序的时间复杂度是多少 ？
// 极端的例子：如果数组中的数据原来已经是有序的了，比如 1，3，5，6，8。如果我们每次选择最后一个元素作为 pivot，那每次分区得到的两个区间都是不均等的。
// 我们需要进行大约 n 次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约 n / 2 个元素，这种情况下，快排的时间复杂度就从 O(nlogn) 退化成了 O(n2)。
// 最佳情况：T(n) = O(nlogn)。
// 最差情况：T(n) = O(n2)。
// 平均情况：T(n) = O(nlogn)。


// 可以发现：
    // 归并排序的处理过程是由下而上的，先处理子问题，然后再合并。
    // 而快排正好相反，它的处理过程是由上而下的，先分区，然后再处理子问题。
    // 归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。
    // 归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。
    // 快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
        



</script>